As modern circuit networks shrink in physical dimensions and element counts (transistors, gates, wires) increase exponentially over time, testing a chip for defects after fabrication has become increasingly important and complex. Current state of the art incorporates automated testers which scan computer or hand-generated test cases (known as test vectors) into scan-latches within the circuit network. Generally, scannable memory elements, such as scan-latches, are those elements whose values can be directly observed during a test process. These scannable memory elements are employable to reveal logic values of the circuit blocks under test.
Through employment of known input values, fed into a particular logic function, an output measured by the automated tester can be compared to an expected result. Correspondence of measured results with expected results verifies correct operation of the device.
The physical topology of the circuit network, particularly the arrangement and operation of scannable memory elements, helps to determine the complexity of the test patterns used for verification, the time required for testing each chip, and the quality of those tests in terms of potential faults covered.
Feedback that crosses a particular class of network elements, however, is a physical topology which makes this verification process extremely difficult. Feedback crossing a network element can be generally defined as a feedback loop containing the network element. Feedback across non-scan latches (NSLS)—memory elements whose stored values cannot be directly observed or altered during the test process—pose problems to test pattern generation, test time and test quality.
When a network of logic elements driven by an NSL is fed back to the input of that same NSL, a loop is created that can make testing the circuit networks involved very difficult. Generally, the output value of the NSL at time tn, known as F(tn), depends on the input F(tn−1) because of feedback. F(tn−1) in turn depends on F(tn−2) in a regression all the way back to the initial state F(0). If this initial state is unknown, testing can be impossible. Even if the initial state is known, however, all values F(0) to F(tn) (or at a minimum, all the values before some known pattern begins to repeat) should be known by the test pattern generation program in order to determine the next expected output of the circuit network F(tn+1). Obtaining and retaining the output values is very costly in terms of compute time and memory, respectively. However, not retaining this information can be even more costly. Not retaining the output values means that the node of logic involved in the loop cannot be tested and, as a result, may have errors that will go unnoticed until use by a customer.
Feedback crossing scannable latches (SLs), however, effectively short-circuits this infinite loop. With SLs, known values can be injected into the circuit network loop at any time and the output can be tested for correspondence to these known inputs. Because it does not pose any special difficulty for test pattern generation, feedback across a scannable element is generally permitted in circuit networks.
A circuit network can be modeled as a directed graph, wherein the nodes or vertices of the graph are the circuit elements (transistors, gates, and so on), while the edges of the graph are the wires, buses or nets of the circuit network. Generally, directed graph is traversed by entering an input pin to the circuit network. A breadth first traversal can be performed from the input. Generally, a breadth first traversal can be defined as visiting and marking all unvisited elements a distance of one from the input, then all unvisited elements a distance of two from the input, and so on. Unvisited elements can generally be defined as a state wherein the element has not yet been visited by the directed graph during a traversal.
However, in the run time of such breadth first traversal algorithms, quadratic O(N2) time is typically required to find feedback cycles in a directed graph. Here, N equals the number of network elements plus the number of wires or nets connecting those elements. With circuit networks where N is in the range of hundreds of millions to billions of elements, this run time is unacceptably slow. Enormous run time in the case of the O(N2) breadth first traversal algorithm means that few, if any, of the detrimental feedback cycles crossing non-scan latches will be detected. This in turn makes the circuit network harder to test, diminishes test coverage and increases test time.
As feedback loops cross non-scannable elements, it is desirable to find and eliminate such loops prior to fabrication. Therefore, what is needed is a feedback detector that overcomes the limitations of conventional feedback detectors.